/*  naive_chains.h
 * Copyright (C) 2010, Francisco Claude & Patrick Nicholson, all rights reserved.
 *
 * Francisco Claude & Patrick Nicholson <(fclaude|p3nichol)@cs.uwaterloo.ca>
 *
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include<iostream>
#include<fstream>
#include<sstream>
#include<algorithm>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<cassert>
#include<cmath>

using namespace std;

#include "point.h"
#include "search.h"
#include "geometry.h"

#ifndef NAIVECHAINS_H
#define NAIVECHAINS_H

/** Class for representing the u-chains structure.
 * It does assume that the chains are untangled and does not make use of any fancy technique like fractional cascading.
 */
class NaiveChains {
  public:
    /** Reads a u-chains structure created by build_index */
    NaiveChains(ifstream & input);
    /** Destroys the structure */
    ~NaiveChains();
    /** Returns the average number of points per chain */
    double getAvgNumPointsPerChain() const;
    /** Returns the std dev of the number of points per chain */
    double getStdDevOfPointsPerChain() const;
    /** Return the number of chains */
    size_t getNumChains() const;
    /** Returns the number of points */
    size_t getNumPoints() const;
    /** Returns the size in bytes */
    size_t getSize() const;
    /** Searches doing binary search in every chain */
    vector<Point> search(const Point & p1, const Point & p2) const;
    /** Adaptive search over the chains */
    vector<Point> adaptiveSearch(const Point & p1, const Point & p2) const;
    /** Brute force search over the chains (linear over every chain) */
    vector<Point> naiveSearch(const Point & p1, const Point & p2) const;
  protected:
    size_t achainsLen;
    size_t * alength;
    Point ** achains;
    size_t dchainsLen;
    size_t * dlength;
    Point ** dchains;
    size_t totalPoints;
    double dminx, dminy, dmaxx, dmaxy;
    double aminx, aminy, amaxx, amaxy;

};

#endif

